package backtrack;

import java.util.ArrayList;
import java.util.List;

/**
 * 基础子集型问题
 */
public class Solution_78 {

    private List<List<Integer>> res = new ArrayList<>();

    public List<List<Integer>> subsets(int[] nums) {
        List<Integer> path = new ArrayList<>();
//        backtrack1(nums, 0, path);
        backtrack2(nums, 0, path);
        return res;
    }

    /**
     * 当前操作：枚举下标大于等于start的数，加入path   ，下一次操作枚举下标大于等于start+1的
     * <p>
     * 1.视角
     * 站在当前层看“还有哪些元素可以加入”，然后逐个尝试。
     * 每一层 for-loop 的  i  就是“本次要加入 path 的那个下标”。
     * 2.递归树形态
     * 每个节点代表一个“待选列表”  nums[start … end] ，分支数等于剩余元素个数。
     * 树的深度 = 元素个数，宽度逐渐变窄。
     * 3.去重/顺序
     * i + 1  天然保证后面的元素不会再被本轮使用 → 元素只出现一次且升序排列，因此子集没有重复。
     * 4.何时用
     * • 需要“组合”、“子集”类问题（无序，元素最多用一次）。
     * • 想顺带做“按字典序输出”或“同层去重”时，只需在 for 循环里加判断即可
     */
    private void backtrack1(int[] nums, int start, List<Integer> path) {
        res.add(new ArrayList<>(path));
        for (int i = start; i < nums.length; i++) {
            path.add(nums[i]);
            backtrack1(nums, i + 1, path);
            path.remove(path.size() - 1);
        }
    }

    /**
     * 当前操作：枚举第i个数选或不选
     * <p>
     * 1.视角
     * 站在当前元素  nums[start]  上问“我要不要”把它放进 path。
     * 每层只有两个分支：左子树“跳过”，右子树“选”。
     * 2.递归树形态
     * 二叉树，深度 = 元素个数，每层固定只有两个分叉。
     * 所有叶子节点就是 2ⁿ 个子集。
     * 3.去重/顺序
     * 由于每次只处理一个元素，且元素互不相同，天然不会重复；
     * 顺序固定为原始下标顺序，不会乱序。
     * 4.何时用
     * • 想用最简洁的代码生成所有子集（两行分支搞定）。
     * • 需要“选/不选”这种明确决策语义时更直观（比如后面改成分割等值和、位运算等）
     */
    private void backtrack2(int[] nums, int start, List<Integer> path) {
        if (start == nums.length) {
            res.add(new ArrayList<>(path));
            return;
        }
        path.add(nums[start]);
        backtrack2(nums, start + 1, path);
        path.remove(path.size() - 1);

        backtrack2(nums, start + 1, path);

    }

    public static void main(String[] args) {
        Solution_78 solution78 = new Solution_78();
        List<List<Integer>> subsets = solution78.subsets(new int[]{1, 2, 3});
        subsets.forEach(list -> {
            list.forEach(System.out::print);
            System.out.println();
        });
    }
}
